1. Field of the Invention
The present invention relates in general to a convolutional interleaver or deinterleaver for rearranging bytes forming words of an input word sequence to produce an output word sequence, and in particular to a convolutional interleaver or deinterleaver employing both a direct memory accessed external memory and an internal cache memory for temporarily storing bytes of the input word sequence until they are incorporated into the output word sequence.
2. Description of Related Art
FIG. 1 depicts a typical prior art communication system including a transmitter 10 for converting an input data sequence TX into an outgoing analog signal V1 transmitted through a communication channel 14 to a receiver 12. Receiver 12 converts signal V2 back into an output data sequence RX matching the transmitters' incoming data sequence TX. Since channel 14 can introduce random noise into signal V2, it is possible that some of the bits of the RX sequence will not match corresponding bits of the TX sequence. To reduce the likelihood that noise in channel 14 will produce errors in the RX sequence, transmitter 10 includes a forward error correction (FEC) encoder 16, such as for example a Reed-Solomon encoder, for encoding the incoming data sequence TX into a sequence A of N-byte words. Each word of sequence A “over-represents” a corresponding portion of the TX sequence because it contains redundant data. A convolutional interleaver 18 interleaves bytes of successive words of word sequence A to produce an output word sequence B supplied to a modulator 20. Modulator 20 generates signal V1 to represent successive bytes of word sequence B. A demodulator 22 within receiver 12 demodulates signal V2 to produce a word sequence B′. Word sequence B′ will nominally match the word sequence B input to the transmitter's modulator 20, though some of the bytes forming word sequence B′ may include bit errors caused by noise in channel 14. A deinterleaver circuit 24 deinterleaves word sequence B′ to produce a word sequence A′ nominally matching word sequence A, although it too may include errors resulting from the errors in word sequence B′. An FEC decoder 26 then decodes word sequence A′ to produce the output data sequence RX.
Although the A′ sequence may contain some errors, it is possible for FEC decoder 26 to produce an outgoing sequence RX matching the TX sequence because words of the A′ sequence contain redundant data. When a portion of an A′ sequence word representing any particular portion of the RX data is corrupted due to an error in the B′ sequence, another redundant portion of the A′ sequence word also representing that particular portion of the RX sequence may not be corrupted. FEC decoder 26 is able to determine which portions of each A′ sequence word are not corrupted and uses the uncorrupted portions of those words as a basis for determining bit values of its corresponding portion the RX sequence. Each possible FEC scheme will have a limited capability for correcting byte errors. For example, a (255, 16) Reed-Solomon code, including 16 bytes of redundant data to form a 255 bytes code word can correct up to 8 byte errors, but no more.
It is possible for some portion of the RX sequence to contain an error when there are excessive errors within an A′ sequence word representing that particular portion of the RX sequence, but interleaver 18 and deinterleaver 24 help to reduce the chances of that happening. Since noise in channel 14 can occur in bursts that may persist long enough to corrupt portions of signal V1 conveying every byte of a B′ sequence word, interleaver 18 improves the system's noise immunity by interleaving bytes of successive words of sequence A to produce word sequence B. Since each word of sequence A produced by FEC encoder 16 contains redundant data describing a particular section of the TX sequence, interleaving the words of sequence A to produce words of sequence B has the effect of spreading out information conveyed by signal V1 so that a single noise burst in channel 14 is less likely to corrupt an excessive number of bytes of information representing the same portion of the TX sequence.
FIG. 2 shows an example of how interleaver 18 might rearrange bytes of sequence A to produce sequence B. In this example each ith word Ai of sequence A includes five bytes Ai,0 through Ai,4 and each ith word of sequence B has five bytes Bi,0 through Bi,4. This particular interleaving scheme has an “interleaving depth” D=4 because as shown in FIG. 2 the five bytes of each word Ai of sequence A appear as every fourth byte of sequence B. Since the longest noise burst the system can tolerate is a function of how widely interleaver 18 separates the data in sequence B, the noise tolerance of the system increases with interleaving depth D.
When interleaver 18 has an interleaving depth D it must delay each jth byte Ai,j of each ith word Ai of sequence A by (D−1)×j bytes to form a byte of sequence B. Since interleaver 18 must store a byte in order to delay it, the number of bytes of sequence A interleaver 18 must concurrently store increases with interleaving depth D. When interleaver 18 stores each word of sequence A until it no longer needs any byte of that word to produce a word of sequence B, then the total number of bytes interleaver 18 must concurrently store is N×D where N is the number of bytes per word. Deinterleaver 24 will require a similar internal storage capacity to deinterleave the B′ sequence. Thus, the noise immunity interleaver 18 and deinterleaver 24 can provide is a function of its storage capacity.
FIG. 3 illustrates a prior art interleaver 18 including a controller 28, an input buffer 30, a static random access memory (SRAM) 32 and an output buffer 34 all of which may be implemented on the same integrated circuit (IC) 35. FEC encoder 16 (FIG. 1) writes successive bytes of each successive word of sequence A into input buffer 30, and whenever it has written an entire word of sequence A into buffer 30 it pulses an INPUT_READY input signal to controller 28. Controller 28 responds to the INPUT_READY signal by writing each byte of the sequence A word in buffer 30 to a separate address of SRAM 32. Controller 28 then sequentially reads each byte that is to form a next word of sequence B out of SRAM 32, stores it in output buffer 34 and then sends an OUTPUT_READY signal to modulator 20 (FIG. 1) telling it that it may read a next word of sequence B out of output buffer 34.
The algorithm controller 28 employs for producing read and write addresses for SDRAM 32 ensures that each incoming word of sequence A into SRAM 32 overwrites a previous word of sequence A that is no longer needed and ensures that bytes forming words of sequence B are read in the proper order. To interleave N-byte words of incoming sequence A with an interleaving depth D, SRAM 32 must have D×N addressable byte storage locations. The interleaver architecture illustrated in FIG. 3 is typically employed when interleaver 18 can be implemented on a single IC 35, but when N×D is large it becomes impractical to embed a sufficiently large SDRAM 32 in a single IC.
FIG. 4 illustrates another prior art architecture for an interleaver 18′ including a controller 28′, an input buffer 30′ and an output buffer 34′ included within a single IC 35′. Interleaver 18′ employs an external synchronous dynamic random access memory (SDRAM) 36 for storing bytes rather than an internal SRAM. While controller 28 of FIG. 3 can directly read and write accesses each byte of SRAM 32, controller 28′ of FIG. 4 can only access data in SDRAM 36 via a direct memory access (DMA) controller 38. Rather than individually read and write accessing each byte stored in SDRAM 36, DMA controller 38 operates in a “burst” mode wherein it read or write accesses bytes stored at several (typically 16) successive addresses. Thus when controller 28′ wants to obtain particular bytes stored in SDRAM 36 to write into output buffer 34′, it must ask DMA controller 38 to read a block of bytes including the particular bytes needed to form the next output sequence word. Controller 28′ then transfers those particular bytes to output buffer 34′. However since bytes are not addressed in SDRAM in the order in which they are needed to from bytes of the outgoing word sequence, many of the bytes DMA controller 38 reads from SDRAM 36 during each DMA read access will be discarded.
Deinterleaver 24 of FIG. 1 may have the same topology as interleaver 18 of FIG. 3 or of FIG. 4, with the controller 28 or 28′ of the deinterleaver implementing an algorithm that deinterleaves the B′ sequence to produce the A′ sequence.
Since SDRAMs are relatively inexpensive, it can be more cost effective for an interleaver or deinterleaver to employ the architecture of FIG. 4 than that of FIG. 3, particularly when a large amount of memory is needed. However since read and write access to an internal SRAM is typically faster than that of an external SDRAM, interleaver 18 of FIG. 3 can have a higher throughput (in bytes per second) than interleaver 18′ of FIG. 4. The maximum throughput of the interleaver of FIG. 4 can be further limited because much of the bandwidth of SDRAM 36 is wasted reading bytes that are discarded.
What is needed is an interleaver or deinterleaver employing a DMA controller to access an inexpensive external memory, but which improves its data throughput by making more efficient use of its DMA data transfer bandwidth.